package org.example.array;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Vector;

public class Solution {
    public int pivotIndex(int[] stArray) {
        for (int i = 0; i < stArray.length; i++) {
            int front = getfront(i, stArray);
            int back = getback(i, stArray);
            if (front == back) {
                return i;
            }
        }
        return -1;
    }

    private int getfront(int i, int[] stArray) {
        int result = 0;
        for (int j = i + 1; j < stArray.length; j++) {
            result = result + stArray[j];
        }
        return result;
    }

    private int getback(int i, int[] stArray) {
        int result = 0;
        for (int k = 0; k < i; k++) {
            result = result + stArray[k];
        }
        return result;
    }

    public int pivotIndex2(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count = count + nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            if(getfront(i, nums) * 2 + nums[i] == count){
                return i;
            }
        }
        return -1;
    }

    public int pivotIndex3(int[] nums) {
        int count = 0;
        int front = 0;
        for (int i = 0; i < nums.length; i++) {
            count = count + nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            if (front * 2 + nums[i] == count) {
                return i;
            }
            front = front + nums[i];
        }
        return -1;
    }

    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (target <= nums[i]) {
                return i;
            }
        }
        return nums.length;
    }

    public int searchInsert2(int[] nums, int target) {
        // 二分法
        int left = 0, right = nums.length - 1;
        while(left <= right){
            // 防止 left+right 整型溢出
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }
        }
        return left;
    }

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return intervals;
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));//按每行的第0列升序排序
        Vector<int[]> integerVector;//由于我们事先不知道数组大小，所以用Vector类实现动态数组。
        integerVector = new Vector<>();
        int[] ints = intervals[0];//定义一个Int类型数组用于作比较，默认值为第一组二维数组的值。
        for (int i = 1; i < intervals.length; i++) {//循环这个二维数组
            if (ints[1] >= intervals[i][0]) {//如果第一个数组的右端点大于等于下一个数组的左端点，做说明两个数组有所交集。
                ints[1] = Math.max(ints[1], intervals[i][1]);//int类型数组的右端点等于两个数组中右端点大的那个值。
            } else {
                integerVector.add(ints);//把int类型一维数组ints添加到我们创建的vector类里面。
                ints = intervals[i];//给一维数组重新赋值。
            }
        }
        integerVector.add(ints);//把最后一个区间添加到Vector里面
        return integerVector.toArray(new int[integerVector.size()][2]);//把vector转换成二维数组返回。
    }
}
